package com.duanjw.algorithms;

import java.util.Iterator;

/**
 * 队列
 * 先进先出
 *
 * @author duanjw
 */
public class Queue<T> implements Iterable<T> {
    /**
     * 第一个元素
     */
    private Node first;
    /**
     * 栈中第一个元素
     */
    private Node last;
    /**
     * 栈长度
     */
    private int size;

    /**
     * 添加一个元素
     *
     * @param t
     */
    public void enqueue(T t) {
        Node oldLast = last;
        last = new Node();
        last.t = t;
        last.next = null;
        if (isEmpty()) {
            first = last;
        } else {
            oldLast.next = last;
        }
        size++;
    }

    /**
     * 删除最近添加的元素
     *
     * @return
     */
    public T dequeue() {
        T t = first.t;
        first = first.next;
        if (isEmpty()) {
            last = null;
        }
        size--;
        return t;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node current = first;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                T t = current.t;
                current = current.next;
                return t;
            }
        };
    }

    /**
     * 单向链表
     */
    private class Node {
        private T t;
        private Node next;
    }
}
